/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        if(!pHead)  return NULL;
        //直接法：时间复杂度O(n*n)
        /*
        创建一个数组用于存储各节点，每次扫描到新节点都要与数组中已知节点比较；
        若有相等的情况出现，则意味着找到了环的入口
        */
        vector<ListNode*> numOfList;//用于保存链表各节点
        while(pHead){
            if(isLoop(numOfList, pHead))  return pHead;
            numOfList.push_back(pHead);
            pHead = pHead->next;
        }
        return NULL;
    }
    
    //寻找环
    bool isLoop(vector<ListNode*>& numOfList, ListNode* pHead){
        int length = numOfList.size();
        if(length == 0)  return false;
        for(int i = 0; i < length - 1; ++i){
            if(numOfList[i] == pHead)  return true;
        }
        return false;
    }
};

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        if(!pHead)  return NULL;
        //双指针法：时间复杂度O(n)
        /*
        创建两个指针fast、slow，fast一次走两步，slow一次走一步，若slow能追上fast，则证明有环；
        若环中有n个结点，则让fast先走n步，fast、slow之间保持距离n，则当slow进入环入口时，fast
        刚好也到达环的入口;
        确定环的节点数：当fast、slow第一次相遇时，保持一个不懂，另一个开始移动直到重新相遇，统计
        环中节点数;
        */
        ListNode* fast = pHead;
        ListNode* slow = pHead;
        
        bool hasLoop = false;
        while(fast && fast->next){
            fast = fast->next->next;  //fast每次走两步
            slow = slow->next;  //slow每次走一步
            if(fast == slow){
                hasLoop = true;
                break;
            }
        }
        
        //判断环中节点个数并寻找入口
        if(hasLoop){
            int numsOfLoop = 1;
            while(fast->next != slow){
                ++numsOfLoop;
                fast = fast->next;
            }
            
            //重置指针，从头开始
            fast = pHead;
            slow = pHead;
            for(int i = 0; i < numsOfLoop; ++i)  fast = fast->next;
            while(fast != slow){
                fast = fast->next;
                slow = slow->next;
            }
            return fast;  //环的出口
        }
        return NULL;
    }
};